//力扣-目标和问题的01背包解法2-使用二维的dp数组

/*
没有完成！！
*/

#include <iostream>
#include <vector>
#include <string.h>
#include <math.h>
using namespace std;
int backpack01(vector<int>& nums, int target, vector<vector<int> > &dp);
int findTargetSumWays(vector<int>& nums, int S);

int findTargetSumWays(vector<int>& nums, int S) {
    int sum = 0;
    for (unsigned int i = 0; i < nums.size(); i++) {
        sum += nums[i];
    }
    if (S > sum || (S + sum) % 2 != 0){
        return 0;
    }
    int x = (S + sum) / 2;
    if (x < 0) return 0;

    vector<vector<int> > dp(nums.size()+1, vector<int>(x+1, 0));

    for (unsigned int i = 0; i <= nums.size(); i++) {
        dp[i][0] = 1;        
    }
    return backpack01(nums, x, dp); 
}
int backpack01(vector<int>& nums, int target, vector<vector<int> > &dp) {
    for (unsigned int i = 1; i <= nums.size(); i++) {
        for (int j = 0; j <= target; j++) {
            int num = nums[i-1];
            
        }
    }
    return dp[nums.size()][target];
}

int main(){
    vector<int> nums = {0, 0, 0, 0, 0, 0, 0, 0, 1};
    int S = 1;
    cout << findTargetSumWays(nums, S) << endl;
    return 0;
}